
class Solution {
public:
    vector<int> v;
    int ret = 0;
    int reversePairs(vector<int>& record) {
        v.resize(record.size());
        Mergesort(record, 0, v.size() - 1);
        return ret;
    }
    void Mergesort(vector<int>& num, int left, int right)
    {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        Mergesort(num, left, mid);
        Mergesort(num, mid + 1, right);
        int begin1 = left, begin2 = mid + 1;
        while (begin1 <= mid && begin2 <= right)
        {
            if (num[begin1] / 2.0 > num[begin2])
            {
                begin1++;
                ret += right - begin2 + 1;
            }
            else
            {
                begin2++;
            }
        }
        int cur2 = mid + 1, cur1 = left, i = left;
        while (cur1 <= mid && cur2 <= right)
            v[i++] = num[cur1] > num[cur2] ? num[cur1++] : num[cur2++];
        while (cur1 <= mid)  v[i++] = num[cur1++];
        while (cur2 <= right) v[i++] = num[cur2++];
        for (int x = left; x <= right; x++)
            num[x] = v[x];
    }
};
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode* n1 = NULL;
    ListNode* n2 = head;
    ListNode* n3 = head->next;
    while (n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}